We present a novel spectral learning algorithm for simultaneous localization and mapping (SLAM) from range data with known correspondences. This algorithm is an instance of a general spectral system identification framework, from which it inherits several desirable properties, including statistical consistency and no local optima. Compared with popular batch optimization or multiple-hypothesis tracking (MHT) methods for range-only SLAM, our spectral approach offers guaranteed low computational requirements and good tracking performance. Compared with popular extended Kalman filter (EKF) or extended information filter (EIF) approaches, and many MHT ones, our approach does not need to linearize a transition or measurement model; such linearizations can cause severe errors in EKFs and EIFs, and to a lesser extent MHT, particularly for the highly non-Gaussian posteriors encountered in range-only SLAM. We provide a theoretical analysis of our method, including finite-sample error bounds. Finally, we demonstrate on a real-world robotic SLAM problem that our algorithm is not only theoretically justified, but works well in practice: in a comparison of multiple methods, the lowest errors come from a combination of our algorithm with batch optimization, but our method alone produces nearly as good a result at far lower computational cost. 1 Introduction In range-only SLAM, we are given a sequence of range measurements from a robot to fixed landmarks, and possibly a matching sequence of odometry measurements. We then attempt to simultaneously estimate the robot's trajectory and the locations of the landmarks. In all the above approaches, the most popular representation for a hypothesis is a list of landmark locations (m n,x,m n,y) and a list of robot poses (x t,y t,θ t) . Unfortunately, both the motion and measurement models are highly nonlinear in this representation, leading to computational problems: inaccurate linearizations in EKF/EIF/MHT and local optima in batch optimization approaches (see Section 2 for details). Much work has attempted to remedy this problem, e.g., by changing the hypothesis representation (Djugash, 2010) or by keeping multiple hypotheses (Djugash et al., 2005; Djugash, 2010; Thrun et al., 2005). While considerable progress has been made, none of these methods are ideal; common difficulties include the need for an extensive initialization phase, inability to recover from poor initialization, lack of performance guarantees, or excessive computational requirements. We take a very different approach: we formulate range-only SLAM as a matrix factorization problem, where features of observations are linearly related to a 4-or 7-dimensional state space.

Combinatorial optimization is widely applied in a number of areas nowadays. Unfortunately, many combinatorial optimization problems are NP-hard which usually means that they are unsolvable in practice. However, it is often unnecessary to have an exact solution. In this case one may use heuristic approach to obtain a near-optimal solution in some reasonable time. We focus on two combinatorial optimization problems, namely the Generalized Traveling Salesman Problem and the Multidimensional Assignment Problem. The first problem is an important generalization of the Traveling Salesman Problem; the second one is a generalization of the Assignment Problem for an arbitrary number of dimensions. Both problems are NP-hard and have hosts of applications. In this work, we discuss different aspects of heuristics design and evaluation. A broad spectrum of related subjects, covered in this research, includes test bed generation and analysis, implementation and performance issues, local search neighborhoods and efficient exploration algorithms, metaheuristics design and population sizing in memetic algorithm. The most important results are obtained in the areas of local search and memetic algorithms for the considered problems. In both cases we have significantly advanced the existing knowledge on the local search neighborhoods and algorithms by systematizing and improving the previous results. We have proposed a number of efficient heuristics which dominate the existing algorithms in a wide range of time/quality requirements. Several new approaches, introduced in our memetic algorithms, make them the state-of-the-art metaheuristics for the corresponding problems. Population sizing is one of the most promising among these approaches; it is expected to be applicable to virtually any memetic algorithm.

A multiple attribute decision making (MADM), in which attributes are real number, interval real number, linguistic and uncertain linguistic value, has been already applied in practice such as the evaluation of enterprise effect, the selection of investment project, the selection of person, the research of military equipment scheme, the evaluation of strategy effect, the reliability assessment and the maintainability assessment, etc (Yongqi Xia, 2004, Dang Luo, Sifeng Liu, 2005, Yongqing Wei, Peide Liu, 2009). Extended TOPSIS Method with Interval-Valued Intuitionistic Fuzzy Numbers for Virtual Enterprise Partner Selection has been researched by Fei Ye(2010). Chuanming Ding (2007,a) defined a new similarity degree for various types of attribute and normalized the calculation of similarity degree of the attribute value of each type in unified metric space. Also, by this similarity degree, the comparison of each plan with ideal plan was performed and decision making method was given. Chuanming (2007,b), based on the TOPSIS (Technique for Order Preference by Similarity to Ideal Solution), transformed the attribute value of plan into four-dimensional attribute value, unified various types of attribute value, defined a fourdimensional approach degree, and by this approach degree, solved the multiple attribute mixed-type decision-making problem associated with real number, interval real number, linguistic and uncertain linguistic value. Yongqi Xia (2004) studied a method considering insufficiency degree of information and preference to danger on the basis of the grey-fuzzy comprehensive evaluation method of interval value preference. In the method, they represent the weight and the attribute value by two interval number pair by considering membership and grey degree at the same time. Sifeng Liu, Yaoguo Dang, Jiangling Wang, Zhengpeng Wu (2009), based on the definitions of entropy, proposed a method of getting weight that considers the character of grey cluster decision-making and 2-tuple linguistic assessment, and proposed the method of 2-tuple linguistic assessment based on grey cluster. Zhen Zhang, Chonghui Guo (2012) transformed uncertain linguistic evaluation information of each decision maker to trapezoidal fuzzy numbers, and then denoted, by solving two optimization models, the collective evaluation of the alternatives by trapezoidal fuzzy numbers.

Can one parallelize complex exploration exploitation tradeoffs? As an example, consider the problem of optimal high-throughput experimental design, where we wish to sequentially design batches of experiments in order to simultaneously learn a surrogate function mapping stimulus to response and identify the maximum of the function. We formalize the task as a multi-armed bandit problem, where the unknown payoff function is sampled from a Gaussian process (GP), and instead of a single arm, in each round we pull a batch of several arms in parallel. We develop GP-BUCB, a principled algorithm for choosing batches, based on the GP-UCB algorithm for sequential GP optimization. We prove a surprising result; as compared to the sequential approach, the cumulative regret of the parallel algorithm only increases by a constant factor independent of the batch size B. Our results provide rigorous theoretical support for exploiting parallelism in Bayesian global optimization. We demonstrate the effectiveness of our approach on two real-world applications.

Recent work on approximate linear programming (ALP) techniques for first-order Markov Decision Processes (FOMDPs) represents the value function linearly w.r.t. a set of first-order basis functions and uses linear programming techniques to determine suitable weights. This approach offers the advantage that it does not require simplification of the first-order value function, and allows one to solve FOMDPs independent of a specific domain instantiation. In this paper, we address several questions to enhance the applicability of this work: (1) Can we extend the first-order ALP framework to approximate policy iteration to address performance deficiencies of previous approaches? (2) Can we automatically generate basis functions and evaluate their impact on value function quality? (3) How can we decompose intractable problems with universally quantified rewards into tractable subproblems? We propose answers to these questions along with a number of novel optimizations and provide a comparative empirical evaluation on logistics problems from the ICAPS 2004 Probabilistic Planning Competition.

The paper introduces a penalized matrix estimation procedure aiming at solutions which are sparse and low-rank at the same time. Such structures arise in the context of social networks or protein interactions where underlying graphs have adjacency matrices which are block-diagonal in the appropriate basis. We introduce a convex mixed penalty which involves $\ell_1$-norm and trace norm simultaneously. We obtain an oracle inequality which indicates how the two effects interact according to the nature of the target matrix. We bound generalization error in the link prediction problem. We also develop proximal descent strategies to solve the optimization problem efficiently and evaluate performance on synthetic and real data sets.

Most prior work on active learning of classifiers has focused on sequentially selecting one unlabeled example at a time to be labeled in order to reduce the overall labeling effort. In many scenarios, however, it is desirable to label an entire batch of examples at once, for example, when labels can be acquired in parallel. This motivates us to study batch active learning, which iteratively selects batches of $k>1$ examples to be labeled. We propose a novel batch active learning method that leverages the availability of high-quality and efficient sequential active-learning policies by attempting to approximate their behavior when applied for $k$ steps. Specifically, our algorithm first uses Monte-Carlo simulation to estimate the distribution of unlabeled examples selected by a sequential policy over $k$ step executions. The algorithm then attempts to select a set of $k$ examples that best matches this distribution, leading to a combinatorial optimization problem that we term "bounded coordinated matching". While we show this problem is NP-hard in general, we give an efficient greedy solution, which inherits approximation bounds from supermodular minimization theory. Our experimental results on eight benchmark datasets show that the proposed approach is highly effective

This paper analyzes the problem of Gaussian process (GP) bandits with deterministic observations. The analysis uses a branch and bound algorithm that is related to the UCB algorithm of (Srinivas et al, 2010). For GPs with Gaussian observation noise, with variance strictly greater than zero, Srinivas et al proved that the regret vanishes at the approximate rate of $O(1/\sqrt{t})$, where t is the number of observations. To complement their result, we attack the deterministic case and attain a much faster exponential convergence rate. Under some regularity assumptions, we show that the regret decreases asymptotically according to $O(e^{-\frac{\tau t}{(\ln t)^{d/4}}})$ with high probability. Here, d is the dimension of the search space and tau is a constant that depends on the behaviour of the objective function near its global maximum.

Given two views (or representations) of the same set of objects, it aims at finding projections for each representation such that their correlation is maximized in the projection space. As every popular method in machine learning, since its first formulation (Hotelling, 1936) CCA has been extended to a kernel version (Lai & Fyfe, 2000; Akaho, 2001), to online and recursive versions (V ıa et al., 2007) and quite recently to a sparse version (Hardoon & Shawe-Taylor, 2011). CCA is usually formulated as the Generalized Singular Value Decomposition (Generalized SVD) of the cross-covariance matrix (Sun et al., 2009). Besides, it aims at finding projections that are orthogonal with respect to the auto-covariance matrices of each view. As CCA belongs to the class of Latent Variables methods, it shares close connections with those methods. Indeed, according to Rosipal & Kr amer (2006); Sun et al. (2009), CCA is a generalization of Orthonormal-ized Partial Least Squares.

As machine learning algorithms enter applications in industrial settings, there is increased interest in controlling their cpu-time during testing. The cpu-time consists of the running time of the algorithm and the extraction time of the features. The latter can vary drastically when the feature set is diverse. In this paper, we propose an algorithm, the Greedy Miser, that incorporates the feature extraction cost during training to explicitly minimize the cpu-time during testing. The algorithm is a straightforward extension of stage-wise regression and is equally suitable for regression or multi-class classification. Compared to prior work, it is significantly more cost-effective and scales to larger data sets.