OpenRaiser/Intern-Atlas huggingface dataset:
Momentum Control with Hierarchical Inverse Dynamics on a Torque-Controlled Humanoid
Venue: arXiv cs.RO 2015
Year: 2015

Hierarchical inverse dynamics based on cascades of quadratic programs have been proposed for the control of legged robots. They have important benefits but to the best of our knowledge have never been implemented on a torque controlled humanoid where model inaccuracies, sensor noise and real-time computation requirements can be problematic. Using a reformulation of existing algorithms, we propose a simplification of the problem that allows to achieve real-time control. Momentum-based control is integrated in the task hierarchy and a LQR design approach is used to compute the desired associated closed-loop behavior and improve performance. Extensive experiments on various balancing and tracking tasks show very robust performance in the face of unknown disturbances, even when the humanoid is standing on one foot. Our results demonstrate that hierarchical inverse dynamics together with momentum control can be efficiently used for feedback control under real robot conditions.
Neuroevolution in Games: State of the Art and Open Challenges
Venue: arXiv cs.NE 2015
Year: 2015

This paper surveys research on applying neuroevolution (NE) to games. In neuroevolution, artificial neural networks are trained through evolutionary algorithms, taking inspiration from the way biological brains evolved. We analyse the application of NE in games along five different axes, which are the role NE is chosen to play in a game, the different types of neural networks used, the way these networks are evolved, how the fitness is determined and what type of input the network receives. The article also highlights important open research challenges in the field.
Higher-order MRFs based image super resolution: why not MAP?
Venue: arXiv cs.CV 2015
Year: 2015

A trainable filter-based higher-order Markov Random Fields (MRFs) model - the so called Fields of Experts (FoE), has proved a highly effective image prior model for many classic image restoration problems. Generally, two options are available to incorporate the learned FoE prior in the inference procedure: (1) sampling-based minimum mean square error (MMSE) estimate, and (2) energy minimization-based maximum a posteriori (MAP) estimate. This letter is devoted to the FoE prior based single image super resolution (SR) problem, and we suggest to make use of the MAP estimate for inference based on two facts: (I) It is well-known that the MAP inference has a remarkable advantage of high computational efficiency, while the sampling-based MMSE estimate is very time consuming. (II) Practical SR experiment results demonstrate that the MAP estimate works equally well compared to the MMSE estimate with exactly the same FoE prior model. Moreover, it can lead to even further improvements by incorporating our discriminatively trained FoE prior model. In summary, we hold that for higher-order natural image prior based SR problem, it is better to employ the MAP estimate for inference.
Parallel training of DNNs with Natural Gradient and Parameter Averaging
Venue: arXiv cs.NE 2015
Year: 2015

We describe the neural-network training framework used in the Kaldi speech recognition toolkit, which is geared towards training DNNs with large amounts of training data using multiple GPU-equipped or multi-core machines. In order to be as hardware-agnostic as possible, we needed a way to use multiple machines without generating excessive network traffic. Our method is to average the neural network parameters periodically (typically every minute or two), and redistribute the averaged parameters to the machines for further training. Each machine sees different data. By itself, this method does not work very well. However, we have another method, an approximate and efficient implementation of Natural Gradient for Stochastic Gradient Descent (NG-SGD), which seems to allow our periodic-averaging method to work well, as well as substantially improving the convergence of SGD on a single machine.
Does Google Scholar contain all highly cited documents (1950-2013)?
Venue: arXiv cs.DL 2015
Year: 2015

The study of highly cited documents on Google Scholar (GS) has never been addressed to date in a comprehensive manner. The objective of this work is to identify the set of highly cited documents in Google Scholar and define their core characteristics: their languages, their file format, or how many of them can be accessed free of charge. We will also try to answer some additional questions that hopefully shed some light about the use of GS as a tool for assessing scientific impact through citations. The decalogue of research questions is shown below: 1. Which are the most cited documents in GS? 2. Which are the most cited document types in GS? 3. What languages are the most cited documents written in GS? 4. How many highly cited documents are freely accessible? 4.1 What file types are the most commonly used to store these highly cited documents? 4.2 Which are the main providers of these documents? 5. How many of the highly cited documents indexed by GS are also indexed by WoS? 6. Is there a correlation between the number of citations that these highly cited documents have received in GS and the number of citations they have received in WoS? 7. How many versions of these highly cited documents has GS detected? 8. Is there a correlation between the number of versions GS has detected for these documents, and the number citations they have received? 9. Is there a correlation between the number of versions GS has detected for these documents, and their position in the search engine result pages? 10. Is there some relation between the positions these documents occupy in the search engine result pages, and the number of citations they have received?
Symmetric low-rank representation for subspace clustering
Venue: arXiv cs.CV 2015
Year: 2015

We propose a symmetric low-rank representation (SLRR) method for subspace clustering, which assumes that a data set is approximately drawn from the union of multiple subspaces. The proposed technique can reveal the membership of multiple subspaces through the self-expressiveness property of the data. In particular, the SLRR method considers a collaborative representation combined with low-rank matrix recovery techniques as a low-rank representation to learn a symmetric low-rank representation, which preserves the subspace structures of high-dimensional data. In contrast to performing iterative singular value decomposition in some existing low-rank representation based algorithms, the symmetric low-rank representation in the SLRR method can be calculated as a closed form solution by solving the symmetric low-rank optimization problem. By making use of the angular information of the principal directions of the symmetric low-rank representation, an affinity graph matrix is constructed for spectral clustering. Extensive experimental results show that it outperforms state-of-the-art subspace clustering algorithms.
Refined Upper Bounds on Stopping Redundancy of Binary Linear Codes
Venue: arXiv cs.IT 2015
Year: 2015

The $l$-th stopping redundancy $ρ_l(\mathcal C)$ of the binary $[n, k, d]$ code $\mathcal C$, $1 \le l \le d$, is defined as the minimum number of rows in the parity-check matrix of $\mathcal C$, such that the smallest stopping set is of size at least $l$. The stopping redundancy $ρ(\mathcal C)$ is defined as $ρ_d(\mathcal C)$. In this work, we improve on the probabilistic analysis of stopping redundancy, proposed by Han, Siegel and Vardy, which yields the best bounds known today. In our approach, we judiciously select the first few rows in the parity-check matrix, and then continue with the probabilistic method. By using similar techniques, we improve also on the best known bounds on $ρ_l(\mathcal C)$, for $1 \le l \le d$. Our approach is compared to the existing methods by numerical computations.
On Kernelization and Approximation for the Vector Connectivity Problem
Venue: arXiv cs.CC 2015
Year: 2015

In the Vector Connectivity problem we are given an undirected graph $G=(V,E)$, a demand function $ϕ\colon V\to\{0,\ldots,d\}$, and an integer $k$. The question is whether there exists a set $S$ of at most $k$ vertices such that every vertex $v\in V\setminus S$ has at least $ϕ(v)$ vertex-disjoint paths to $S$; this abstractly captures questions about placing servers or warehouses relative to demands. The problem is \NP-hard already for instances with $d=4$ (Cicalese et al., arXiv '14), admits a log-factor approximation (Boros et al., Networks '14), and is fixed-parameter tractable in terms of~$k$ (Lokshtanov, unpublished '14). We prove several results regarding kernelization and approximation for Vector Connectivity and the variant Vector $d$-Connectivity where the upper bound $d$ on demands is a fixed constant. For Vector $d$-Connectivity we give a factor $d$-approximation algorithm and construct a vertex-linear kernelization, i.e., an efficient reduction to an equivalent instance with $f(d)k=O(k)$ vertices. For Vector Connectivity we have a factor $\text{opt}$-approximation and we can show that it has no kernelization to size polynomial in $k$ or even $k+d$ unless $\mathsf{NP\subseteq coNP/poly}$, making $f(d)\operatorname{poly}(k)$ optimal for Vector $d$-Connectivity. Finally, we provide a write-up for fixed-parameter tractability of Vector Connectivity($k$) by giving an alternative FPT algorithm based on matroid intersection.
Simple and Effective Type Check Removal through Lazy Basic Block Versioning
Venue: arXiv cs.PL 2015
Year: 2015

Dynamically typed programming languages such as JavaScript and Python defer type checking to run time. In order to maximize performance, dynamic language VM implementations must attempt to eliminate redundant dynamic type checks. However, type inference analyses are often costly and involve tradeoffs between compilation time and resulting precision. This has lead to the creation of increasingly complex multi-tiered VM architectures. This paper introduces lazy basic block versioning, a simple JIT compilation technique which effectively removes redundant type checks from critical code paths. This novel approach lazily generates type-specialized versions of basic blocks on-the-fly while propagating context-dependent type information. This does not require the use of costly program analyses, is not restricted by the precision limitations of traditional type analyses and avoids the implementation complexity of speculative optimization techniques. We have implemented intraprocedural lazy basic block versioning in a JavaScript JIT compiler. This approach is compared with a classical flow-based type analysis. Lazy basic block versioning performs as well or better on all benchmarks. On average, 71% of type tests are eliminated, yielding speedups of up to 50%. We also show that our implementation generates more efficient machine code than TraceMonkey, a tracing JIT compiler for JavaScript, on several benchmarks. The combination of implementation simplicity, low algorithmic complexity and good run time performance makes basic block versioning attractive for baseline JIT compilers.
Correlation Clustering with Constrained Cluster Sizes and Extended Weights Bounds
Venue: arXiv cs.LG 2015
Year: 2015

We consider the problem of correlation clustering on graphs with constraints on both the cluster sizes and the positive and negative weights of edges. Our contributions are twofold: First, we introduce the problem of correlation clustering with bounded cluster sizes. Second, we extend the regime of weight values for which the clustering may be performed with constant approximation guarantees in polynomial time and apply the results to the bounded cluster size problem.
Ethical Artificial Intelligence
Venue: arXiv cs.AI 2015
Year: 2015

This book-length article combines several peer reviewed papers and new material to analyze the issues of ethical artificial intelligence (AI). The behavior of future AI systems can be described by mathematical equations, which are adapted to analyze possible unintended AI behaviors and ways that AI designs can avoid them. This article makes the case for utility-maximizing agents and for avoiding infinite sets in agent definitions. It shows how to avoid agent self-delusion using model-based utility functions and how to avoid agents that corrupt their reward generators (sometimes called "perverse instantiation") using utility functions that evaluate outcomes at one point in time from the perspective of humans at a different point in time. It argues that agents can avoid unintended instrumental actions (sometimes called "basic AI drives" or "instrumental goals") by accurately learning human values. This article defines a self-modeling agent framework and shows how it can avoid problems of resource limits, being predicted by other agents, and inconsistency between the agent's utility function and its definition (one version of this problem is sometimes called "motivated value selection"). This article also discusses how future AI will differ from current AI, the politics of AI, and the ultimate use of AI to help understand the nature of the universe and our place in it.
Minimax Estimation of Discrete Distributions under $\ell_1$ Loss
Venue: arXiv cs.IT 2015
Year: 2015

We analyze the problem of discrete distribution estimation under $\ell_1$ loss. We provide non-asymptotic upper and lower bounds on the maximum risk of the empirical distribution (the maximum likelihood estimator), and the minimax risk in regimes where the alphabet size $S$ may grow with the number of observations $n$. We show that among distributions with bounded entropy $H$, the asymptotic maximum risk for the empirical distribution is $2H/\ln n$, while the asymptotic minimax risk is $H/\ln n$. Moreover, Moreover, we show that a hard-thresholding estimator oblivious to the unknown upper bound $H$, is asymptotically minimax. However, if we constrain the estimates to lie in the simplex of probability distributions, then the asymptotic minimax risk is again $2H/\ln n$. We draw connections between our work and the literature on density estimation, entropy estimation, total variation distance ($\ell_1$ divergence) estimation, joint distribution estimation in stochastic processes, normal mean estimation, and adaptive estimation.
Efficient Estimation of Mutual Information for Strongly Dependent Variables
Venue: arXiv cs.IT 2015
Year: 2015

We demonstrate that a popular class of nonparametric mutual information (MI) estimators based on k-nearest-neighbor graphs requires number of samples that scales exponentially with the true MI. Consequently, accurate estimation of MI between two strongly dependent variables is possible only for prohibitively large sample size. This important yet overlooked shortcoming of the existing estimators is due to their implicit reliance on local uniformity of the underlying joint distribution. We introduce a new estimator that is robust to local non-uniformity, works well with limited data, and is able to capture relationship strengths over many orders of magnitude. We demonstrate the superior performance of the proposed estimator on both synthetic and real-world data.
Price Competition, Fluctuations, and Welfare Guarantees
Venue: arXiv cs.GT 2015
Year: 2015

In various markets where sellers compete in price, price oscillations are observed rather than convergence to equilibrium. Such fluctuations have been empirically observed in the retail market for gasoline, in airline pricing and in the online sale of consumer goods. Motivated by this, we study a model of price competition in which an equilibrium rarely exists. We seek to analyze the welfare, despite the nonexistence of an equilibrium, and present welfare guarantees as a function of the market power of the sellers. We first study best response dynamics in markets with sellers that provide a homogeneous good, and show that except for a modest number of initial rounds, the welfare is guaranteed to be high. We consider two variations: in the first the sellers have full information about the valuation of the buyer. Here we show that if there are $n$ items available across all sellers and $n_{\max}$ is the maximum number of items controlled by any given seller, the ratio of the optimal welfare to the achieved welfare will be at most $\log(\frac{n}{n-n_{\max}+1})+1$. As the market power of the largest seller diminishes, the welfare becomes closer to optimal. In the second variation we consider an extended model where sellers have uncertainty about the buyer's valuation. Here we similarly show that the welfare improves as the market power of the largest seller decreases, yet with a worse ratio of $\frac{n}{n-n_{\max}+1}$. The exponential gap in welfare between the two variations quantifies the value of accurately learning the buyer valuation. Finally, we show that extending our results to heterogeneous goods in general is not possible. Even for the simple class of $k$-additive valuations, there exists a setting where the welfare approximates the optimal welfare within any non-zero factor only for $O(1/s)$ fraction of the time, where $s$ is the number of sellers.
A new estimate of mutual information based measure of dependence between two variables: properties and fast implementation
Venue: arXiv cs.IT 2015
Year: 2015

This article proposes a new method to estimate an existing mutual information based dependence measure using histogram density estimates. Finding a suitable bin length for histogram is an open problem. We propose a new way of computing the bin length for histogram using a function of maximum separation between points. The chosen bin length leads to consistent density estimates for histogram method. The values of density thus obtained are used to calculate an estimate of an existing dependence measure. The proposed estimate is named as Mutual Information Based Dependence Index (MIDI). Some important properties of MIDI have also been stated. The performance of the proposed method has been compared to generally accepted measures like Distance Correlation (dcor), Maximal Information Coefficient (MINE) in terms of accuracy and computational complexity with the help of several artificial data sets with different amounts of noise. The proposed method is able to detect many types of relationships between variables, without making any assumption about the functional form of the relationship. The power statistics of proposed method illustrate their effectiveness in detecting non linear relationship. Thus, it is able to achieve generality without a high rate of false positive cases. MIDI is found to work better on a real life data set than competing methods. The proposed method is found to overcome some of the limitations which occur with dcor and MINE. Computationally, MIDI is found to be better than dcor and MINE, in terms of time and memory, making it suitable for large data sets.
Amoeba Techniques for Shape and Texture Analysis
Venue: arXiv cs.CV 2015
Year: 2015

Morphological amoebas are image-adaptive structuring elements for morphological and other local image filters introduced by Lerallut et al. Their construction is based on combining spatial distance with contrast information into an image-dependent metric. Amoeba filters show interesting parallels to image filtering methods based on partial differential equations (PDEs), which can be confirmed by asymptotic equivalence results. In computing amoebas, graph structures are generated that hold information about local image texture. This paper reviews and summarises the work of the author and his coauthors on morphological amoebas, particularly their relations to PDE filters and texture analysis. It presents some extensions and points out directions for future investigation on the subject.
Error-Correction Capability of Reed-Muller codes
Venue: arXiv cs.IT 2015
Year: 2015

We present an asymptotic limit between correctable and uncor-rectable errors on the Reed-Muller codes of any order. This limit is theoretical and does not depend of any decoding algorithm.
Promise problems solved by quantum and classical finite automata
Venue: arXiv cs.FL 2015
Year: 2015

The concept of promise problems was introduced and started to be systematically explored by Even, Selman, Yacobi, Goldreich, and other scholars. It has been argued that promise problems should be seen as partial decision problems and as such that they are more fundamental than decision problems and formal languages that used to be considered as the basic ones for complexity theory. The main purpose of this paper is to explore the promise problems accepted by classical, quantum and also semi-quantum finite automata. More specifically, we first introduce two acceptance modes of promise problems, recognizability and solvability, and explore their basic properties. Afterwards, we show several results concerning descriptional complexity on promise problems. In particular, we prove: (1) there is a promise problem that can be recognized exactly by measure-once one-way quantum finite automata (MO-1QFA), but no deterministic finite automata (DFA) can recognize it; (2) there is a promise problem that can be solved with error probability $ε\leq 1/3$ by one-way finite automaton with quantum and classical states (1QCFA), but no one-way probability finite automaton (PFA) can solve it with error probability $ε\leq 1/3$; and especially, (3) there are promise problems $A(p)$ with prime $p$ that can be solved {\em with any error probability} by MO-1QFA with only two quantum basis states, but they can not be solved exactly by any MO-1QFA with two quantum basis states; in contrast, the minimal PFA solving $A(p)$ with any error probability (usually smaller than $1/2$) has $p$ states. Finally, we mention a number of problems related to promise for further study.
An Examination And Report On Potential Methods Of Strategic Location-Based Service Applications On Mobile Networks And Devices
Venue: arXiv cs.CY 2015
Year: 2015

Mobile technologies are growing significantly in past few years. Many new features and enhancement have implemented in mobile technologies in both software and hardware aspects. Nowadays, cell phones are not just only use for making calls or sending text messages, however, technologies behind mobile phones expanded vastly which facilitate them to offer various types of services. Location-based service is one of the most popular mobile technologies which equipped in new generation of hand phones. The main focus of this paper is to review various strategic location-based applications on mobile networks and devices.
On the absence of the RIP in real-world applications of compressed sensing and the RIP in levels
Venue: arXiv cs.IT 2015
Year: 2015

The purpose of this paper is twofold. The first is to point out that the Restricted Isometry Property (RIP) does not hold in many applications where compressed sensing is successfully used. This includes fields like Magnetic Resonance Imaging (MRI), Computerized Tomography, Electron Microscopy, Radio Interferometry and Fluorescence Microscopy. We demonstrate that for natural compressed sensing matrices involving a level based reconstruction basis (e.g. wavelets), the number of measurements required to recover all $s$-sparse signals for reasonable $s$ is excessive. In particular, uniform recovery of all $s$-sparse signals is quite unrealistic. This realisation shows that the RIP is insufficient for explaining the success of compressed sensing in various practical applications. The second purpose of the paper is to introduce a new framework based on a generalised RIP-like definition that fits the applications where compressed sensing is used. We show that the shortcomings that show that uniform recovery is unreasonable no longer apply if we instead ask for structured recovery that is uniform only within each of the levels. To examine this phenomenon, a new tool, termed the 'Restricted Isometry Property in Levels' is described and analysed. Furthermore, we show that with certain conditions on the Restricted Isometry Property in Levels, a form of uniform recovery within each level is possible. Finally, we conclude the paper by providing examples that demonstrate the optimality of the results obtained.