Representations are at the heart of artificial intelligence (AI). This book is devoted to the problem of representation discovery: how can an intelligent system construct representations from its experience? Representation discovery re-parameterizes the state space - prior to the application of information retrieval, machine learning, or optimization techniques - facilitating later inference processes by constructing new task-specific bases adapted to the state space geometry. This book presents a general approach to representation discovery using the framework of harmonic analysis, in particular Fourier and wavelet analysis. Biometric compression methods, the compact disc, the computerized axial tomography (CAT) scanner in medicine, JPEG compression, and spectral analysis of time-series data are among the many applications of classical Fourier and wavelet analysis. A central goal of this book is to show that these analytical tools can be generalized from their usual setting in (infinite-dimensional) Euclidean spaces to discrete (finite-dimensional) spaces typically studied in many subfields of AI. Generalizing harmonic analysis to discrete spaces poses many challenges: a discrete representation of the space must be adaptively acquired; basis functions are not pre-defined, but rather must be constructed. Algorithms for efficiently computing and representing bases require dealing with the curse of dimensionality. However, the benefits can outweigh the costs, since the extracted basis functions outperform parametric bases as they often reflect the irregular shape of a particular state space. Case studies from computer graphics, information retrieval, machine learning, and state space planning are used to illustrate the benefits of the proposed framework, and the challenges that remain to be addressed. Representation discovery is an actively developing field, and the author hopes this book will encourage other researchers to explore this exciting area of research. Table of Contents: Overview / Vector Spaces / Fourier Bases on Graphs / Multiscale Bases on Graphs / Scaling to Large Spaces / Case Study: State-Space Planning / Case Study: Computer Graphics / Case Study: Natural Language / Future Directions
Author(s): Sridhar Mahadevan
Series: Synthesis Lectures on Artificial Intelligence and Machine Learning
Edition: 1
Publisher: Morgan and Claypool Publishers
Year: 2008
Language: English
Pages: 160
Overview......Page 14
WHAT IS A REPRESENTATION?......Page 15
PRINCIPLES OF REPRESENTATION DISCOVERY......Page 16
OVERVIEW OF THE BOOK......Page 17
Theory of Basis Construction: Vector Spaces......Page 19
Algorithms and Computational Tractability......Page 20
Case Studies......Page 21
BIBLIOGRAPHICAL REMARKS......Page 23
Approximating 3D Objects in Computer Graphics......Page 24
Abstract Fourier Expansion......Page 25
Issues in Basis Construction and Selection......Page 26
DUAL BASES......Page 27
LINEAR MAPPINGS AND MATRIX REPRESENTATIONS......Page 29
INVARIANT SUBSPACES......Page 32
Dual Bases and Direct Sum Decompositions......Page 33
Eigenspace Decomposition......Page 35
Singular Value Decomposition......Page 37
Normed spaces......Page 38
Inner Product Spaces......Page 39
Projections onto Finite-Dimensional Spaces......Page 40
Projections in Infinite-Dimensional Hilbert Spaces......Page 41
Reproducing Kernel Hilbert Spaces......Page 42
BIBLIOGRAPHICAL REMARKS......Page 43
ANALYSIS--SYNTHESIS PERSPECTIVE REVISITED......Page 44
Function Approximation Using Laplacian Eigenfunctions......Page 46
RANDOM WALKS AND THE LAPLACIAN......Page 48
Variational Analysis of Laplacian Eigenfunctions......Page 49
GRAPH PARTITIONING AND CHEEGER CONSTANTS......Page 51
BIBLIOGRAPHICAL REMARKS......Page 52
Multiscale Bases on Graphs......Page 53
INTRODUCTION......Page 54
MULTI-RESOLUTION ANALYSIS AND SYNTHESIS......Page 55
Multi-resolution Analysis on Graphs......Page 56
DIFFUSION ANALYSIS......Page 57
Multiscale Analysis of Functions and Stochastic Processes......Page 60
Construction of Diffusion Wavelets......Page 61
Multiscale Compression of a Simple Markov Chain......Page 66
Comparison of Eigenfunction and Diffusion Wavelet Bases......Page 67
BIBLIOGRAPHICAL REMARKS......Page 68
Scaling to Large Spaces......Page 69
KRONECKER SUM DECOMPOSITION......Page 70
Product Spaces: Complex Graphs from Simple Ones......Page 71
Kronecker Product Approximation......Page 74
SCALING TO CONTINUOUS SPACES......Page 75
Manifolds......Page 76
Hodge Theorem......Page 77
THE NYSTRÖM INTERPOLATION OF EIGENFUNCTIONS......Page 78
SAMPLING TECHNIQUES......Page 82
EXPLOITING DOMAIN KNOWLEDGE......Page 83
BIBLIOGRAPHICAL REMARKS......Page 84
Case Study: State-Space Planning......Page 85
INTRODUCTION......Page 86
MARKOV DECISION PROCESSES......Page 87
Hilbert Space Formulation of Value Function Approximation......Page 89
Least-Squares Approximation of Action-Value Functions......Page 91
REPRESENTATION POLICY ITERATION......Page 92
Sample Run of RPI on the Two-Room Environment......Page 93
Comparison with Hand-coded Parametric Bases......Page 95
Factored Representation Policy Iteration for Structured Domains......Page 97
Experimental Results......Page 98
Three Control Tasks......Page 100
Comparing PVFs with RBFs on Continuous MDPs......Page 103
Policy and Reward-Sensitive PVFs......Page 104
Extensions of Proto-Value Functions......Page 105
Preliminaries......Page 106
Direct Solution of Bellman's Equation......Page 107
Experiments......Page 108
BIBLIOGRAPHICAL REMARKS......Page 111
Case Study: Computer Graphics......Page 112
SPECTRAL MESH COMPRESSION: FOURIER VERSUS WAVELET BASES......Page 113
Global Laplacian Eigenfunctions......Page 115
SCALING TO LARGE GRAPHS USING GRAPH PARTITIONING......Page 116
MESH COMPRESSION USING FOURIER AND WAVELET BASES......Page 117
Compression of Small Objects......Page 118
Partition Size Versus Error......Page 119
Compression of Large Objects......Page 120
SUMMARY......Page 121
BIBLIOGRAPHICAL REMARKS......Page 122
Case Study: Natural Language......Page 123
INTRODUCTION......Page 124
Latent Semantic Indexing......Page 126
MULTISCALE ANALYSIS OF TEXT USING DIFFUSION WAVELETS......Page 127
Advantages of the Diffusion Wavelet Approach......Page 128
Diffusion Model: Test 1......Page 131
Diffusion Model: Test 2......Page 135
Running Times for Various Approaches......Page 137
CONCLUSIONS......Page 139
BIBLIOGRAPHICAL REMARKS......Page 141
COMPRESSED SENSING......Page 142
HARMONIC ANALYSIS AND LOGIC......Page 144
GROUP REPRESENTATION THEORY......Page 146
BIBLIOGRAPHICAL REMARKS......Page 149
