Manifold learning theory and applications.pdf-资料库

91c49aef-5ed1-4c61-a3ea-7982220ddd99.pdf-第1页.png

第1页 / 共322页

91c49aef-5ed1-4c61-a3ea-7982220ddd99.pdf-第2页.png

第2页 / 共322页

91c49aef-5ed1-4c61-a3ea-7982220ddd99.pdf-第3页.png

第3页 / 共322页

91c49aef-5ed1-4c61-a3ea-7982220ddd99.pdf-第4页.png

第4页 / 共322页

91c49aef-5ed1-4c61-a3ea-7982220ddd99.pdf-第5页.png

第5页 / 共322页

91c49aef-5ed1-4c61-a3ea-7982220ddd99.pdf-第6页.png

第6页 / 共322页

91c49aef-5ed1-4c61-a3ea-7982220ddd99.pdf-第7页.png

第7页 / 共322页

91c49aef-5ed1-4c61-a3ea-7982220ddd99.pdf-第8页.png

第8页 / 共322页

Manifold LearningTheory and Applications

This page intentionally left blank This page intentionally left blank

CRC Press Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 © 2012 by Taylor & Francis Group, LLC CRC Press is an imprint of Taylor & Francis Group, an Informa business No claim to original U.S. Government works Version Date: 20111110 International Standard Book Number-13: 978-1-4398-7110-2 (eBook - PDF) This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the valid- ity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint. Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or uti- lized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopy- ing, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, please access www.copyright.com (http:// www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Visit the Taylor & Francis Web site at http://www.taylorandfrancis.com and the CRC Press Web site at http://www.crcpress.com

Contents List of Figures List of Tables Preface Editors Contributors 1 Spectral Embedding Methods for Manifold Learning Alan Julian Izenman 1.1 1.2 Spaces and Manifolds Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 Topological Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.2 Topological Manifolds . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.3 Riemannian Manifolds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.4 Curves and Geodesics 1.3 Data on Manifolds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Linear Manifold Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.1 Principal Component Analysis 1.4.2 Multidimensional Scaling . . . . . . . . . . . . . . . . . . . . . . . . 1.5 Nonlinear Manifold Learning . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.1 Isomap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.2 Local Linear Embedding . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.3 Laplacian Eigenmaps . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.4 Diﬀusion Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.5 Hessian Eigenmaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.6 Nonlinear PCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.7 Acknowledgment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v xi xvii xix xxi xxiii 1 1 3 3 4 5 6 7 7 8 11 14 15 20 22 23 26 27 32 32 32

vi Contents 2 Robust Laplacian Eigenmaps Using Global Information Shounak Roychowdhury and Joydeep Ghosh 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Graph Laplacian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Deﬁnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Laplacian of Graph Sum . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Global Information of Manifold . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Laplacian Eigenmaps with Global Information . . . . . . . . . . . . . . . . 2.5 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.1 LEM Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.2 GLEM Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.7 Bibliographical and Historical Remarks . . . . . . . . . . . . . . . . . . . . Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Density Preserving Maps Arkadas Ozakin, Nikolaos Vasiloglou II, Alexander Gray 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 The Existence of Density Preserving Maps . . . . . . . . . . . . . . . . . . . 3.2.1 Moser’s Theorem and Its Corollary on Density Preserving Maps . . 3.2.2 Dimensional Reduction to Rd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.3 3.3 Density Estimation on Submanifolds . . . . . . . . . . . . . . . . . . . . . . 3.3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2 Motivation for the Submanifold Estimator . . . . . . . . . . . . . . . 3.3.3 Statement of the Theorem . . . . . . . . . . . . . . . . . . . . . . . . 3.3.4 Curse of Dimensionality in KDE . . . . . . . . . . . . . . . . . . . . Intuition on Non-Uniqueness 3.4 Preserving the Estimated Density: The Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.2 The Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Bibliographical and Historical Remarks . . . . . . . . . . . . . . . . . . . . Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Sample Complexity in Manifold Learning Hariharan Narayanan 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Sample Complexity of Classiﬁcation on a Manifold . . . . . . . . . . . . . . 4.2.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Learning Smooth Class Boundaries . . . . . . . . . . . . . . . . . . . . . . . 4.3.1 Volumes of Balls in a Manifold . . . . . . . . . . . . . . . . . . . . . 4.3.2 Partitioning the Manifold . . . . . . . . . . . . . . . . . . . . . . . . 4.3.3 Constructing Charts by Projecting onto Euclidean Balls . . . . . . . 4.3.4 Proof of Theorem 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Sample Complexity of Testing the Manifold Hypothesis 37 37 38 38 38 39 40 40 43 47 53 53 54 57 57 58 58 60 60 61 61 61 62 63 64 64 65 67 69 69 71 73 73 74 74 74 74 76 77 77 78 83

Contents 4.5 Connections and Related Work . . . . . . . . . . . . . . . . . . . . . . . . . 4.6 Sample Complexity of Empirical Risk Minimization . . . . . . . . . . . . . 4.6.1 Bounded Intrinsic Curvature . . . . . . . . . . . . . . . . . . . . . . 4.6.2 Bounded Extrinsic Curvature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.7 Relating Bounded Curvature to Covering Number . . . . . . . . . . . . 4.8 Class of Manifolds with a Bounded Covering Number 4.9 Fat-Shattering Dimension and Random Projections . . . . . . . . . . . . . . 4.10 Minimax Lower Bounds on the Sample Complexity . . . . . . . . . . . . . . 4.11 Algorithmic Implications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.11.1 k-Means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.11.2 Fitting Piecewise Linear Curves . . . . . . . . . . . . . . . . . . . . . 4.12 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Manifold Alignment Chang Wang, Peter Kraﬀt, and Sridhar Mahadevan 5.1 5.2 Formalization and Analysis Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1.2 Overview of the Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.1 Loss Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.2 Optimal Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.3 The Joint Laplacian Manifold Alignment Algorithm . . . . . . . . . 5.3 Variants of Manifold Alignment . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.1 Linear Restriction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.2 Hard Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.3 Multiscale Alignment . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.4 Unsupervised Alignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.1 Protein Alignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.2 Parallel Corpora . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.3 Aligning Topic Models . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.6 Bibliographical and Historical Remarks . . . . . . . . . . . . . . . . . . . . 5.7 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Application Examples 6 Large-Scale Manifold Learning Ameet Talwalkar, Sanjiv Kumar, Mehryar Mohri, Henry Rowley 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.2 Nystr¨om Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.3 Column Sampling Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Singular Values and Singular Vectors . . . . . . . . . . . . . . . . . . 6.3.1 6.3.2 Low-Rank Approximation . . . . . . . . . . . . . . . . . . . . . . . . 6.3.3 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4 Large-Scale Manifold Learning . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Comparison of Sampling Methods vii 84 85 85 85 86 86 88 89 91 91 91 91 92 95 95 98 98 99 99 103 103 103 104 106 106 108 109 109 111 114 117 117 118 119 121 121 122 123 124 124 125 125 125 127 129

资料库

Manifold learning theory and applications.pdf

相关推荐

课程资源

热门标签

最新资料